package com.hy.dp;

public class ClimbStairs {


    /**
     * 70. 爬楼梯
     * 力扣题目链接
     *
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     *
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     *
     * 注意：给定 n 是一个正整数。
     *
     * 示例 1：
     *
     * 输入： 2
     * 输出： 2
     * 解释： 有两种方法可以爬到楼顶。
     * 1 阶 + 1 阶
     * 2 阶
     * 示例 2：
     *
     * 输入： 3
     * 输出： 3
     * 解释： 有三种方法可以爬到楼顶。
     * 1 阶 + 1 阶 + 1 阶
     * 1 阶 + 2 阶
     * 2 阶 + 1 阶
     *
     * 思路
     * 本题大家如果没有接触过的话，会感觉比较难，多举几个例子，就可以发现其规律。
     *
     * 爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
     *
     * 那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。
     *
     * 所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。
     *
     * 1.确定dp数组以及下标的含义
     * dp[i]： 爬到第i层楼梯，有dp[i]种方法
     *
     * 2.确定递推公式
     * 如果可以推出dp[i]呢？
     * 所以dp[i] = dp[i - 1] + dp[i - 2] 。
     * 例如强行安慰自己爬到第0层，也有一种方法，什么都不做也就是一种方法即：dp[0] = 1，相当于直接站在楼顶。
     *
     * 3.dp数组如何初始化
     *
     * 4.确定遍历顺序
     * 从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的
     *
     * 5.举例推导dp数组
     * 举例当n为5的时候，dp table（dp数组）应该是这样的
     * @param n
     * @return
     */
    // 常规方式
    public int climbStairs(int n){
        if (n <= 2){
            return n;
        }
        int [] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
    // 用变量记录代替数组
    public int climbStairs2(int n){
        int a = 1,b=1,c= 0;
        for (int i = 2; i < n + 1; i++) {
            // f(i) = f(i - 1) + f(i -2)
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
    // 递归
    public int climbStairs3(int n){
        if (n <= 2){
            return n;
        }
        return climbStairs3(n-1) + climbStairs3(n-2);
    }
    public static void main(String[] args) {
        ClimbStairs climbStairs = new ClimbStairs();
        System.out.println("res: "+climbStairs.climbStairs(4));
        System.out.println("res: "+climbStairs.climbStairs2(4));
        System.out.println("res: "+climbStairs.climbStairs3(4));
    }
}
